package course.p3_arraysSort.exa04_quickSort;

import java.util.Arrays;

public class QuickSort {



    /**
     * 快速排序主函数
     * @param a 目标数组
     * @param Left 开始索引位置
     * @param Right 结束索引位置
     * @param <T> 泛型类型
     * @return
     */
    public static <T extends Comparable<T>> T[] quickSort(T[] a,int Left,int Right) {
        // 特殊情况处理
        if(Left>=Right||Right<0||Left>a.length-1)
            return a;
        int i,j;
        T key;
        // 当排序的元素个数是3个以上
        // 进行快速排序
        if(Left+3 <= Right) {
            key = Median3(a,Left,Right);
            i = Left;
            j = Right-1;
            while (true) {
                while(a[i].compareTo(key) <= 0){
                    if(i < Right) i++;
                    else break;
                }
                while(a[j].compareTo(key) >= 0){
                    if(j > Left) j--;
                    else break;
                }
                if(i < j) {
                    Swap(a,i,j);
                }
                else {
                    //交换i的元素和key
                    Swap(a,i,Right);
                    break;
                }
            }
            int rightLeft = i+1;
            quickSort(a,Left,i-1);//对左边部分进行递归
            quickSort(a,rightLeft, Right);//对右边部分递归
        }
        //当只有2或3个元素时进行简单排序
        else {
            easySort(a,Left,Right);
        }
        return a;
    }



    /**
     * 寻找中值并和最终止位置的元素互换
     * @param a 目标数组
     * @param Left 起始位置
     * @param Right 终止位置
     * @param <T> 类型
     * @return 返回中值
     */
    public static <T extends Comparable<T>> T Median3(T[] a, int Left, int Right) {
        int Center = (Left + Right) / 2;
        if (a[Left].compareTo(a[Center])>=0 && a[Left].compareTo(a[Right])<0 || a[Left].compareTo(a[Center])<0 && a[Left].compareTo(a[Right])>=0) {
            Swap(a, Left, Right);
        } else if (a[Center].compareTo(a[Right])>=0 && a[Center].compareTo(a[Left])<0 || a[Center].compareTo(a[Right])<0 && a[Center].compareTo(a[Left])>=0){
            Swap(a, Center, Right);
        }
        return a[Right];
    }

    /**
     * 交换函数
     * 它交换数组a中j和i位置的元素
     * */
    public static <T extends Comparable<T>> void Swap(T[] a,int j,int i){
        T m;
        m = a[i];
        a[i] = a[j];
        a[j] = m;
    }

    /**
     * 简单排序，它主要解决当要排序的元素数目是2或3个的排序
     * */
    public static <T extends Comparable<T>> void easySort(T[] a,int Left,int Right) {
        int Center = Left+1;
        if(a[Left].compareTo(a[Center])>0) {
            Swap(a,Left,Center);
        }
        if(a[Left].compareTo(a[Right])>0){
            Swap(a,Left,Right);
        }
        if(a[Center].compareTo(a[Right])>0){
            Swap(a,Center,Right);
        }
    }


    public static void quickSortTest() {
        Integer[] numbs = {878, 299, 299, 36, 381, 777, 26, 387, 358, 592};
        quickSort(numbs,0,numbs.length-1);
        System.out.println(Arrays.toString(numbs));
    }

    public static void main(String[] args) {
        quickSortTest();
    }

}
